import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{1,3,-1,-3,5,3,6,7};
        for(int x: s.maxSlidingWindow(nums, 1)) {
            System.out.print(x + " ");
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        /**
         * 滑动窗口最大值*/
        // 1 预处理
        int n = nums.length;
        // -准备单调队列（值：下标）
        Deque<int[]> queue = new LinkedList<>();
        // -准备返回值数组
        int[] retArray = new int[n-k+1];

        // 2 滑动窗口
        int left = 0;
        int right = 0;
        while(right < n) {
            // -1 进窗口
            while(!queue.isEmpty() && queue.peekLast()[0] <= nums[right]) {
                queue.pollLast();
            }
            queue.offerLast(new int[]{nums[right], right});

            // -2 判断（仅当完全窗口时再做处理）
            if(right - left + 1 == k) {
                // -3 更新值
                retArray[right-k+1] = queue.peekFirst()[0];
                left ++;
                while(!queue.isEmpty() && queue.peekFirst()[1] < left) {
                    queue.pollFirst();
                }
            }

            right ++;
        }

        // 3 返回值
        return retArray;
    }
}
